package class05

import (
	"math"
	"sort"
	"strings"
)

/*
	给定两个字符串 s1 和 s2, 问s2最少删除多少个字符串可以成为s1的子串？
	比如：s1 = "abcde", s2 = "axbc"
	返回1，s2 删除掉“x” 就是s1的子串了。

	解法：
		1. 如果字符串s2 比较短，可以采用方案一
		2. 字符串s2较长使用方案二

	方案一：
		获取到s2的所有子序列，并且按长度从大到小排列，然后分别与s1做kmp，求得最小的删除个数。
		复杂度：N*M*N^2  -->  n^3*M
	方案二：
		获取到S1的所有子串，对所有子串与s2做做小编辑距离问题，但是只考虑由删除的场景
		N^2 * N*M ---> n^3*M 存在优化空间，同样的开头的子串公用一张dp表
		可优化至 n^2*M

*/
func DeleteMinCost1(s1, s2 string) int {
	var subSequences []string
	collect := func(s string) {
		subSequences = append(subSequences, s)
	}
	SubSequenceProcess(s2, 0, "", collect)
	sort.Sort(BigLenFirst(subSequences))
	ans := math.MaxInt
	for i:=0; i<len(subSequences); i++ {
		if strings.Index(s1, subSequences[i]) != -1 {
			ans = min(ans, len(s2) - len(subSequences[i]))
		}
	}
	return ans
}

type BigLenFirst []string

func (b BigLenFirst) Len() int {
	return len(b)
}

func (b BigLenFirst) Less(i, j int) bool {
	return len(b[i]) > len(b[j])
}

func (b BigLenFirst) Swap(i, j int)  {
	b[i], b[j] = b[j], b[i]
}

func SubSequenceProcess(s string, start int, path string, collect func(string)){
	if start == len(s) {
		collect(path)
		return
	}
	SubSequenceProcess(s, start+1, path, collect)
	SubSequenceProcess(s, start+1, path+string(s[start]), collect)
}


func DeleteMinCost2(s1, s2 string) int {
	ans := math.MaxInt
	for start:=0; start<len(s1); start++ {
		for end:=start+1; end<len(s1); end++ {
			ans = min(ans, distance(s2, s1[start:end]))
		}
	}
	if ans == math.MaxInt {
		return len(s2)
	}
	return ans
}

/*
	 S2仅采用删除的策略，到s1的最小花费是多少
*/
func distance(s2 string, s1Sub string) int {
	dp := make([][]int, len(s2))
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]int, len(s1Sub))
	}
	if s1Sub[0] == s2[0] {
		dp[0][0] = 0
	} else {
		dp[0][0] = math.MaxInt
	}
	for j:=1; j<len(dp[0]); j++ {
		dp[0][j] = math.MaxInt
	}
	for i:=1; i<len(dp); i++ {
		if dp[i-1][0] != math.MaxInt || s2[i] == s1Sub[0] {
			dp[i][0] = i
		} else {
			dp[i][0] = math.MaxInt
		}
	}
	// dp[i][j]的含义：
	// str2[0..i]仅通过删除行为变成s1sub[0..j]的最小代价
	// 可能性一：
	// str2[0..i]变的过程中，不保留最后一个字符(str2[i])，
	// 那么就是通过str2[0..i-1]变成s1sub[0..j]之后，再最后删掉str2[i]即可 -> dp[i][j] = dp[i-1][j] + 1
	// 可能性二：
	// str2[0..i]变的过程中，想保留最后一个字符(str2[i])，然后变成s1sub[0..j]，
	// 这要求str2[i] == s1sub[j]才有这种可能, 然后str2[0..i-1]变成s1sub[0..j-1]即可
	// 也就是str2[i] == s1sub[j] 的条件下，dp[i][j] = dp[i-1][j-1]
	for i:=1; i<len(dp); i++ {
		for j:=1; j<len(dp[0]); j++ {
			dp[i][j] = math.MaxInt
			if dp[i-1][j] != math.MaxInt {
				dp[i][j] = dp[i-1][j] + 1
			}
			if s2[i] == s1Sub[j] && dp[i-1][j-1] != math.MaxInt{
				dp[i][j] = min(dp[i][j], dp[i-1][j-1])
			}
		}
	}
	return dp[len(s2)-1][len(s1Sub)-1]
}